The background description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the presently named inventors, to the extent the work is described in this background section, as well as aspects of the description that may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as prior art against the present disclosure.
Low density parity check (LDPC) codes are error-correcting codes, which allow data transmitted across a channel to be correctly decoded even when the channel is noisy. LDPC codes encode k bits of user data into an n-bit codeword, where k and n are integers and n is greater than k. The difference (n−k) between n and k determines the number of bits of redundancy of the LDPC code.
An LDPC code, C, may be specified by an m-by-n binary parity check matrix H. For purposes of illustration only, an exemplary 3-by-7 parity check matrix H is shown:
  H  =      [                            1                          1                          1                          1                          1                          1                          1                                      1                          0                          1                          0                          1                          0                          1                                      0                          1                          0                          1                          0                          1                          0                      ]  A binary string c is a codeword in the LDPC code C if and only if Hc={right arrow over (0)}. The length of each codeword is equal to the number of columns, n, of H. In the above example, H has 7 columns, and therefore codewords of the corresponding LDPC code are 7 bits long. For example only, the codeword c=(1,0,1,0,1,0,1)T, where the T signifies a transpose operation, is a codeword in C. This can be verified by multiplying H by cT, and observing that the result is a zero matrix.
The number of rows (m) of H specifies the number of parity check equations of the LDPC code C. Generally, the number of parity check equations of H is greater than or equal to the number of bits of redundancy. In the above example, the number of redundancy bits is 2 instead of 3. This means that the equations of H will be linearly dependent.
Linear dependence can be verified by noting that the linear combination (e.g., XOR) of any two of the rows yields the other row. The above LDPC code therefore encodes 5 bits of user data into a 7-bit codeword. Although the parity check equations of H are linearly dependent in the above example, including an additional equation may improve the accuracy of decoding.
Another example of an LDPC code is specified by the following 4-by-6 parity check matrix:
  H  =      [                            1                          1                          0                          1                          0                          0                                      0                          1                          1                          0                          1                          0                                      1                          0                          1                          0                          0                          1                                      0                          0                          0                          1                          1                          1                      ]  This LDPC code creates codewords of 6 bits each, and includes 4 parity check equations.
LDPC codes provide good bit error rate and frame error rate performance, even at low signal-to-noise ratios. The performance of LDPC codes may be related to the codeword length: longer LDPC codes often outperform shorter codes. However, the encoder/decoder complexity also scales with codeword length. In many applications, such as flash memory, page size continues to increase. For example only, 8 kilobyte pages are now common, which may be too large to practically implement as an LDPC code.